{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum XOR With an Element From Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #trie #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字典树 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximizeXor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #与数组中元素的最大异或值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由非负整数组成的数组 <code>nums</code> 。另有一个查询数组 <code>queries</code> ，其中 <code>queries[i] = [x<sub>i</sub>, m<sub>i</sub>]</code> 。</p>\n",
    "\n",
    "<p>第 <code>i</code> 个查询的答案是 <code>x<sub>i</sub></code> 和任何 <code>nums</code> 数组中不超过 <code>m<sub>i</sub></code> 的元素按位异或（<code>XOR</code>）得到的最大值。换句话说，答案是 <code>max(nums[j] XOR x<sub>i</sub>)</code> ，其中所有 <code>j</code> 均满足 <code>nums[j] &lt;= m<sub>i</sub></code> 。如果 <code>nums</code> 中的所有元素都大于 <code>m<sub>i</sub></code>，最终答案就是 <code>-1</code> 。</p>\n",
    "\n",
    "<p>返回一个整数数组<em> </em><code>answer</code><em> </em>作为查询的答案，其中<em> </em><code>answer.length == queries.length</code><em> </em>且<em> </em><code>answer[i]</code><em> </em>是第<em> </em><code>i</code><em> </em>个查询的答案。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]\n",
    "<strong>输出：</strong>[3,3,7]\n",
    "<strong>解释：</strong>\n",
    "1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。\n",
    "2) 1 XOR 2 = 3.\n",
    "3) 5 XOR 2 = 7.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]\n",
    "<strong>输出：</strong>[15,-1,5]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length, queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= nums[j], x<sub>i</sub>, m<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-xor-with-an-element-from-array](https://leetcode.cn/problems/maximum-xor-with-an-element-from-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-xor-with-an-element-from-array](https://leetcode.cn/problems/maximum-xor-with-an-element-from-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,2,3,4]\\n[[3,1],[1,3],[5,6]]', '[5,2,4,6,6,3]\\n[[12,4],[8,1],[6,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n1, n2 = len(nums), len(queries)\n",
    "        nums.sort()\n",
    "        qes = [(q[1], q[0], i) for i, q in enumerate(queries)]\n",
    "        qes.sort(key=lambda q: q[0])\n",
    "        max_bit = 30\n",
    "        ans = [0] * n2\n",
    "        mask = 0\n",
    "        for k in range(max_bit, -1, -1):\n",
    "            seen = set()\n",
    "            mask |= 1 << k\n",
    "            i = 0\n",
    "            for q in qes:\n",
    "                while i < n1 and nums[i] <= q[0]:\n",
    "                    seen.add(nums[i] & mask)\n",
    "                    i += 1\n",
    "                if i == 0:\n",
    "                    ans[q[2]] = -1\n",
    "                    continue\n",
    "                new_ans = ans[q[2]] | (1 << k)\n",
    "                if new_ans ^ (q[1] & mask) in seen:\n",
    "                    ans[q[2]] = new_ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums.sort()\n",
    "        bit_sets = [set() for _ in range(31)]\n",
    "        j, n = 0, len(nums)\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, m) in sorted(enumerate(queries), key=lambda x: x[1][1]):\n",
    "            while j < n and nums[j] <= m:\n",
    "                for k in range(31):\n",
    "                    bit_sets[k].add(nums[j] >> k)\n",
    "                j += 1\n",
    "            if j == 0:\n",
    "                ans[i] = -1\n",
    "                continue\n",
    "            for k in range(30, -1, -1):\n",
    "                ans[i] = ans[i] * 2 + 1\n",
    "                if ans[i] ^ (x >> k) not in bit_sets[k]:\n",
    "                    ans[i] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums.sort()\n",
    "        bit_sets = [set() for _ in range(31)]\n",
    "        j, n = 0, len(nums)\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, m) in sorted(enumerate(queries), key=lambda x: x[1][1]):\n",
    "            while j < n and nums[j] <= m:\n",
    "                for k in range(31):\n",
    "                    bit_sets[k].add(nums[j] >> k)\n",
    "                j += 1\n",
    "            if j == 0:\n",
    "                ans[i] = -1\n",
    "                continue\n",
    "            for k in range(30, -1, -1):\n",
    "                ans[i] = ans[i] * 2 + 1\n",
    "                if ans[i] ^ (x >> k) not in bit_sets[k]:\n",
    "                    ans[i] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryTrie:\n",
    "    def __init__(self, max_bit: int = 30):\n",
    "        self.to = [[-1], [-1]]\n",
    "        self.cnt = [0]\n",
    "        self.mn = [1 << 63]\n",
    "        self.max_bit = max_bit\n",
    "\n",
    "    def add(self, num: int) -> None:\n",
    "        cur = 0\n",
    "        self.cnt[cur] += 1\n",
    "        self.mn[cur] = min(self.mn[cur], num)\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            if self.to[bit][cur] == -1:\n",
    "                self.to[bit][cur] = len(self.cnt)\n",
    "                self.to[0].append(-1)\n",
    "                self.to[1].append(-1)\n",
    "                self.cnt.append(0)\n",
    "                self.mn.append(1 << 63)\n",
    "            cur = self.to[bit][cur]\n",
    "            self.cnt[cur] += 1\n",
    "            self.mn[cur] = min(self.mn[cur], num)\n",
    "\n",
    "    def remove(self, num: int) -> bool:\n",
    "        if self.cnt[0] == 0: return False\n",
    "        cur = 0\n",
    "        rm = [0]\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0: return False\n",
    "            rm.append(cur)\n",
    "        for cur in rm: self.cnt[cur] -= 1\n",
    "        return True\n",
    "\n",
    "    def count(self, num: int):\n",
    "        cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0: return 0\n",
    "        return self.cnt[cur]\n",
    "\n",
    "    def max_xor(self, x: int, m: int) -> int:\n",
    "        if self.mn[0] > m: return -1\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit ^ 1][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0 or self.mn[nxt] > m:\n",
    "                cur = self.to[bit][cur]\n",
    "            else:\n",
    "                cur = nxt\n",
    "                res |= 1 << k\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        bt = BinaryTrie()\n",
    "        for x in nums:\n",
    "            bt.add(x)\n",
    "        ans =  []\n",
    "        for x, m in queries:\n",
    "            ans.append(bt.max_xor(x, m))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = sorted(set(nums))\n",
    "        order = sorted((m, x, i) for i, (x, m) in enumerate(queries))\n",
    "        maxh = max(nums[-1], max(x for x, _ in queries)).bit_length()\n",
    "        root = [None] * 2\n",
    "        i = 0\n",
    "        ans = [-1] * len(order)\n",
    "        for m, x, idx in order:\n",
    "            if m < nums[0]:\n",
    "                continue\n",
    "\n",
    "            while i < len(nums) and nums[i] <= m:\n",
    "                node = root\n",
    "                for j in range(maxh-1, -1, -1):\n",
    "                    d = nums[i] >> j & 1\n",
    "                    if not node[d]:\n",
    "                        node[d] = [None] * 2\n",
    "                    node = node[d]\n",
    "                i += 1\n",
    "            \n",
    "            node = root\n",
    "            res = 0\n",
    "            for j in range(maxh-1, -1, -1):\n",
    "                d = x >> j & 1\n",
    "                if node[d ^ 1]:\n",
    "                    res |= 1 << j\n",
    "                    node = node[d ^ 1]\n",
    "                else:\n",
    "                    node = node[d]\n",
    "            ans[idx] = res\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\r\n",
    "        s = [{} for _ in range(31)]\r\n",
    "        for no in nums:\r\n",
    "            for i in range(30, -1, -1):\r\n",
    "                if no >> i in s[i]:\r\n",
    "                    s[i][no >> i] = min(s[i][no >> i], no)\r\n",
    "                else:\r\n",
    "                    s[i][no >> i] = no\r\n",
    "        \r\n",
    "        ans = []\r\n",
    "        min_num = min(nums)\r\n",
    "        for x, m in queries:\r\n",
    "            if m < min_num:\r\n",
    "                ans.append(-1)\r\n",
    "                continue\r\n",
    "            t = 0\r\n",
    "            for i in range(30, -1, -1):\r\n",
    "                no = (x >> i) & 1\r\n",
    "                if no == 0:\r\n",
    "                    if 2 * t + 1 in s[i] and s[i][2 * t + 1] <= m:\r\n",
    "                        t = 2 * t + 1\r\n",
    "                    else:\r\n",
    "                        t = 2 * t\r\n",
    "                elif 2 * t in s[i]:\r\n",
    "                    t = 2 * t\r\n",
    "                else:\r\n",
    "                    t = 2 * t + 1\r\n",
    "            ans.append(x ^ t)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = \"children\", \"cnt\"\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, max_bit_length):\n",
    "        self.root = Node()\n",
    "        self.max_bit_length = max_bit_length\n",
    "    \n",
    "    def insert(self, x):\n",
    "        cur = self.root\n",
    "        for i in range(self.max_bit_length-1, -1, -1):\n",
    "            bit = (x>>i) & 1\n",
    "            if cur.children[bit] is None:\n",
    "                cur.children[bit] = Node()\n",
    "            \n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt += 1\n",
    "        return cur\n",
    "    \n",
    "    def remove(self, x):\n",
    "        cur = self.root\n",
    "        for i in range(self.max_bit_length-1, -1, -1):\n",
    "            bit = (x>>i) & 1\n",
    "\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt -= 1\n",
    "        return cur\n",
    "    \n",
    "    def max_xor(self, x):\n",
    "        ans = 0\n",
    "        cur = self.root\n",
    "        for i in range(self.max_bit_length-1, -1, -1):\n",
    "            bit = (x>>i) & 1\n",
    "            if cur.children[bit^1] and cur.children[bit^1].cnt:\n",
    "                ans |= (1<<i)\n",
    "                cur = cur.children[bit^1]\n",
    "            else:\n",
    "                cur = cur.children[bit]\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n,m = len(nums), len(queries)\n",
    "        nums.sort()\n",
    "        queries = sorted([(x, q, i) for i, (x, q) in enumerate(queries)], key=lambda query: query[1])\n",
    "\n",
    "        ans = [0] * m\n",
    "        t = Trie(32)\n",
    "        cur = 0\n",
    "        for x, q, qid in queries:\n",
    "            while cur < n and nums[cur] <= q:\n",
    "                t.insert(nums[cur])\n",
    "                cur += 1\n",
    "\n",
    "            if cur == 0:\n",
    "                ans[qid] = -1\n",
    "\n",
    "            else:\n",
    "                ans[qid] = t.max_xor(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'children', 'cnt'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0\n",
    "\n",
    "class Trie:\n",
    "    HIGH_BIT = 31\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    def insert(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if cur.children[bit] is None:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt += 1\n",
    "        return cur\n",
    "\n",
    "    def remove(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt -= 1\n",
    "        return cur\n",
    "\n",
    "    def Xor(self, val: int) -> int:\n",
    "        cur = self.root\n",
    "        res = 0\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if cur.children[1 - bit] is not None and cur.children[1 - bit].cnt > 0:\n",
    "                cur = cur.children[1 - bit]\n",
    "                res |= (1 - bit) << i\n",
    "            else:\n",
    "                cur = cur.children[bit]\n",
    "                res |= bit << i\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums.sort()\n",
    "        ans = [-1] * len(queries)\n",
    "        left = 0\n",
    "        ZeroOneTrie = Trie()\n",
    "        ids = sorted([i for i in range(len(queries))], key=lambda x:queries[x][1])\n",
    "        for i in ids:\n",
    "            x, m = queries[i]\n",
    "            while left < len(nums) and nums[left] <= m:\n",
    "                ZeroOneTrie.insert(nums[left])\n",
    "                left += 1\n",
    "            if left != 0:\n",
    "                ans[i] = ZeroOneTrie.Xor(x) ^ x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'children', 'cnt'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0\n",
    "    \n",
    "\n",
    "class Tries:\n",
    "    MAX_DIM = 30\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    \n",
    "    def is_empty(self):\n",
    "        if not (self.root.children[0] or self.root.children[1]):\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def insert(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Tries.MAX_DIM - 1, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if not cur.children[bit]:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt += 1\n",
    "    \n",
    "    def remove_one(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Tries.MAX_DIM - 1, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt -= 1\n",
    "    \n",
    "    def max_xor(self, val: int) -> int:\n",
    "        if self.is_empty():\n",
    "            return -1\n",
    "        ans = 0\n",
    "        cur = self.root\n",
    "        for i in range(Tries.MAX_DIM - 1, -1, -1):\n",
    "            bit = bit = (val >> i) & 1\n",
    "            if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt:\n",
    "                ans |= (1 << i)\n",
    "                bit ^= 1\n",
    "            cur = cur.children[bit]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = sorted(nums)\n",
    "        queries = sorted(enumerate(queries), key=lambda x: x[1][1])\n",
    "        ans = [-1] * len(queries)\n",
    "        trie = Tries()\n",
    "        start = 0\n",
    "        for i, (x, m) in queries:\n",
    "            while start < len(nums) and nums[start] <= m:\n",
    "                trie.insert(nums[start])\n",
    "                start += 1\n",
    "            ans[i] = trie.max_xor(x)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BitTrie:\n",
    "    __slots__ = {'bit', 'h'}\n",
    "    def __init__(self, h=31):\n",
    "        self.bit = [None] * 2\n",
    "        self.h = h\n",
    "\n",
    "    def insert(self, num):\n",
    "        node = self\n",
    "        for i in range(self.h-1, -1, -1):\n",
    "            d = num >> i & 1\n",
    "            if not node.bit[d]:\n",
    "                node.bit[d] = BitTrie()\n",
    "            node = node.bit[d]\n",
    "    \n",
    "    def maxxor(self, num):\n",
    "        node = self\n",
    "        ans = 0\n",
    "        for i in range(self.h-1, -1, -1):\n",
    "            d = num >> i & 1\n",
    "            if node.bit[d ^ 1]:\n",
    "                ans |= 1 << i\n",
    "                node = node.bit[d ^ 1]\n",
    "            else:\n",
    "                node = node.bit[d]\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = sorted(set(nums))\n",
    "        order = sorted((m, x, i) for i, (x, m) in enumerate(queries))\n",
    "        maxh = max(nums[-1], max(x for x, _ in queries)).bit_length()\n",
    "        root = BitTrie(maxh)\n",
    "        i = 0\n",
    "        ans = [-1] * len(order)\n",
    "        for m, x, idx in order:\n",
    "            if m < nums[0]:\n",
    "                continue\n",
    "            while i < len(nums) and nums[i] <= m:\n",
    "                root.insert(nums[i])\n",
    "                i += 1\n",
    "            ans[idx] = root.maxxor(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        root = [[],[]]\n",
    "        def add(num):\n",
    "            node = root\n",
    "            for i in range(31,-1,-1):\n",
    "                if num >> i & 1:\n",
    "                    if not node[1]:\n",
    "                        node[1] = [[],[]]\n",
    "                    \n",
    "                    node = node[1]\n",
    "                    \n",
    "                else:\n",
    "                    if not node[0]:\n",
    "                        node[0] = [[],[]]\n",
    "                    node = node[0]\n",
    "        \n",
    "        def find(num):\n",
    "            # 0100\n",
    "            node = root\n",
    "            res = 0\n",
    "            for i in range(31,-1,-1):\n",
    "                if num >> i & 1:\n",
    "                    if node[0]:\n",
    "                        res += (1<<i)\n",
    "                        node = node[0]\n",
    "                    else:\n",
    "                        if node[1]:\n",
    "                            node = node[1]\n",
    "                        else:\n",
    "                            break\n",
    "                else:\n",
    "                    if node[1]:\n",
    "                        res += (1<<i)\n",
    "                        node = node[1]\n",
    "                    else:\n",
    "                        if node[0]:\n",
    "                            node = node[0]\n",
    "                        else:\n",
    "                            break\n",
    "            else:\n",
    "                return res\n",
    "            return -1\n",
    "        \n",
    "        mix = [[i,-1,-1] for i in nums] + [[j,i,ind] for ind,(i,j) in enumerate(queries)]\n",
    "        mix = sorted(mix)\n",
    "        ans = [[]] * len(queries)\n",
    "        for x,y,ind in mix:\n",
    "            if y == -1:\n",
    "                add(x)\n",
    "            else:\n",
    "                ans[ind]=find(y)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    L = 30\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.min_value = float(\"inf\")\n",
    "\n",
    "    def insert(self, val: int):\n",
    "        node = self\n",
    "        node.min_value = min(node.min_value, val)\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if bit == 0:\n",
    "                if not node.left:\n",
    "                    node.left = Trie()\n",
    "                node = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = Trie()\n",
    "                node = node.right\n",
    "            node.min_value = min(node.min_value, val)\n",
    "    \n",
    "    def getMaxXorWithLimit(self, val: int, limit: int) -> int:\n",
    "        node = self\n",
    "        if node.min_value > limit:\n",
    "            return -1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            check = False\n",
    "            if bit == 0:\n",
    "                if node.right and node.right.min_value <= limit:\n",
    "                    node = node.right\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.left and node.left.min_value <= limit:\n",
    "                    node = node.left\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.right\n",
    "            if check:\n",
    "                ans |= 1 << i\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        t = Trie()\n",
    "        for val in nums:\n",
    "            t.insert(val)\n",
    "        \n",
    "        q = len(queries)\n",
    "        ans = [0] * q\n",
    "        for i, (x, m) in enumerate(queries):\n",
    "            ans[i] = t.getMaxXorWithLimit(x, m)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    L = 30\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def insert(self, val: int):\n",
    "        node = self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if bit == 0:\n",
    "                if not node.left:\n",
    "                    node.left = Trie()\n",
    "                node = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = Trie()\n",
    "                node = node.right\n",
    "    \n",
    "    def getMaxXor(self, val: int) -> int:\n",
    "        ans, node = 0, self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            check = False\n",
    "            if bit == 0:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.left:\n",
    "                    node = node.left\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.right\n",
    "            if check:\n",
    "                ans |= 1 << i\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n, q = len(nums), len(queries)\n",
    "        nums.sort()\n",
    "        queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda query: query[1])\n",
    "        \n",
    "        ans = [0] * q\n",
    "        t = Trie()\n",
    "        idx = 0\n",
    "        for x, m, qid in queries:\n",
    "            while idx < n and nums[idx] <= m:\n",
    "                t.insert(nums[idx])\n",
    "                idx += 1\n",
    "            if idx == 0:\n",
    "                # 字典树为空\n",
    "                ans[qid] = -1\n",
    "            else:\n",
    "                ans[qid] = t.getMaxXor(x)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 在线查询 + 字典树\n",
    "class Trie:\n",
    "    L = 30\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.min_value = float(\"inf\")\n",
    "\n",
    "    def insert(self, val: int):\n",
    "        node = self\n",
    "        node.min_value = min(node.min_value, val)\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if bit == 0:\n",
    "                if not node.left:\n",
    "                    node.left = Trie()\n",
    "                node = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = Trie()\n",
    "                node = node.right\n",
    "            node.min_value = min(node.min_value, val)\n",
    "    \n",
    "    def getMaxXorWithLimit(self, val: int, limit: int) -> int:\n",
    "        node = self\n",
    "        if node.min_value > limit:\n",
    "            return -1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            check = False\n",
    "            if bit == 0:\n",
    "                if node.right and node.right.min_value <= limit:\n",
    "                    node = node.right\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.left and node.left.min_value <= limit:\n",
    "                    node = node.left\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.right\n",
    "            if check:\n",
    "                ans |= 1 << i\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        t = Trie()\n",
    "        for val in nums:\n",
    "            t.insert(val)\n",
    "        \n",
    "        q = len(queries)\n",
    "        ans = [0] * q\n",
    "        for i, (x, m) in enumerate(queries):\n",
    "            ans[i] = t.getMaxXorWithLimit(x, m)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.min_val = float('inf')\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "        \n",
    "class Trie:\n",
    "    def __init__(self, nums, depth):\n",
    "        self.depth = depth\n",
    "        self.root = Node()\n",
    "        for num in nums:\n",
    "            self.insert(num)\n",
    "    \n",
    "    def insert(self, num):\n",
    "        node = self.root\n",
    "        node.min_val = min(node.min_val, num)\n",
    "        for i in range(self.depth, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            if bit == 0:\n",
    "                if not node.left:\n",
    "                    node.left = Node()\n",
    "               \tnode = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = Node()\n",
    "                node = node.right\n",
    "            node.min_val = min(node.min_val, num)\n",
    "\n",
    "            \n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        self.depth = 30\n",
    "        self.root = Trie(nums, self.depth).root\n",
    "        return [self.query(*x) for x in queries]\n",
    "    \n",
    "    def query(self, x, m):\n",
    "        cur_val, node = 0, self.root\n",
    "        if node.min_val > m:\n",
    "            return -1\n",
    "        for i in range(self.depth, -1, -1):\n",
    "            bit = (x >> i) & 1\n",
    "            a, b = node.left, node.right\n",
    "            if bit == 0:\n",
    "                a, b = b, a\n",
    "            if a and a.min_val <= m:\n",
    "                node = a\n",
    "                cur_val = (1 << i) | cur_val\n",
    "            else:\n",
    "                node = b\n",
    "        return cur_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 离线查询 + 字典树\n",
    "class Trie:\n",
    "    L = 30\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def insert(self, val: int):\n",
    "        node = self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if bit == 0:\n",
    "                if not node.left:\n",
    "                    node.left = Trie()\n",
    "                node = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = Trie()\n",
    "                node = node.right\n",
    "    \n",
    "    def getMaxXor(self, val: int) -> int:\n",
    "        ans, node = 0, self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            check = False\n",
    "            if bit == 0:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.left:\n",
    "                    node = node.left\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.right\n",
    "            if check:\n",
    "                ans |= 1 << i\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n, q = len(nums), len(queries)\n",
    "        nums.sort()\n",
    "        queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda query: query[1])\n",
    "        \n",
    "        ans = [0] * q\n",
    "        t = Trie()\n",
    "        idx = 0\n",
    "        for x, m, qid in queries:\n",
    "            while idx < n and nums[idx] <= m:\n",
    "                t.insert(nums[idx])\n",
    "                idx += 1\n",
    "            if idx == 0:\n",
    "                # 字典树为空\n",
    "                ans[qid] = -1\n",
    "            else:\n",
    "                ans[qid] = t.getMaxXor(x)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    L = 30\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def insert(self, val: int):\n",
    "        node = self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if bit == 0:\n",
    "                if not node.left:\n",
    "                    node.left = Trie()\n",
    "                node = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = Trie()\n",
    "                node = node.right\n",
    "    \n",
    "    def getMaxXor(self, val: int) -> int:\n",
    "        ans, node = 0, self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            check = False\n",
    "            if bit == 0:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.left:\n",
    "                    node = node.left\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.right\n",
    "            if check:\n",
    "                ans |= 1 << i\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n, q = len(nums), len(queries)\n",
    "        nums.sort()\n",
    "        queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda query: query[1])\n",
    "        \n",
    "        ans = [0] * q\n",
    "        t = Trie()\n",
    "        idx = 0\n",
    "        for x, m, qid in queries:\n",
    "            while idx < n and nums[idx] <= m:\n",
    "                t.insert(nums[idx])\n",
    "                idx += 1\n",
    "            if idx == 0:\n",
    "                # 字典树为空\n",
    "                ans[qid] = -1\n",
    "            else:\n",
    "                ans[qid] = t.getMaxXor(x)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    L = 30\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left = self.right = None\n",
    "\n",
    "    def insert(self, x):\n",
    "        node = self\n",
    "        for i in range(Trie.L)[::-1]:\n",
    "            bit = x >> i & 1\n",
    "            if bit == 0:\n",
    "                if not node.left:\n",
    "                    node.left = Trie()\n",
    "                node = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = Trie()\n",
    "                node = node.right\n",
    "\n",
    "    def search(self, x):\n",
    "        res = 0\n",
    "        node = self\n",
    "        for i in range(Trie.L)[::-1]:\n",
    "            bit = x >> i & 1\n",
    "            check = False\n",
    "            if bit == 0:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.left:\n",
    "                    node = node.left\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.right\n",
    "            if check:\n",
    "                res |= 1 << i\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        j = 0\n",
    "        res = [-1] * len(queries)\n",
    "        tree = Trie()\n",
    "        for i, (x, m) in sorted(enumerate(queries), key=lambda e: e[1][1]):\n",
    "            while j < n and nums[j] <= m:\n",
    "                tree.insert(nums[j])\n",
    "                j += 1\n",
    "            if j == 0:\n",
    "                continue\n",
    "            res[i] = tree.search(x)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    L = 30\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def insert(self, val: int):\n",
    "        node = self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if bit == 0:\n",
    "                if not node.left:\n",
    "                    node.left = Trie()\n",
    "                node = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = Trie()\n",
    "                node = node.right\n",
    "    \n",
    "    def getMaxXor(self, val: int) -> int:\n",
    "        ans, node = 0, self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            check = False\n",
    "            if bit == 0:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.left:\n",
    "                    node = node.left\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.right\n",
    "            if check:\n",
    "                ans |= 1 << i\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n, q = len(nums), len(queries)\n",
    "        nums.sort()\n",
    "        queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda query: query[1])\n",
    "        \n",
    "        ans = [0] * q\n",
    "        t = Trie()\n",
    "        idx = 0\n",
    "        for x, m, qid in queries:\n",
    "            while idx < n and nums[idx] <= m:\n",
    "                t.insert(nums[idx])\n",
    "                idx += 1\n",
    "            if idx == 0:\n",
    "                # 字典树为空\n",
    "                ans[qid] = -1\n",
    "            else:\n",
    "                ans[qid] = t.getMaxXor(x)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    L = 30\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def insert(self, val: int):\n",
    "        node = self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if bit == 0:\n",
    "                if not node.left:\n",
    "                    node.left = Trie()\n",
    "                node = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = Trie()\n",
    "                node = node.right\n",
    "    \n",
    "    def getMaxXor(self, val: int) -> int:\n",
    "        ans, node = 0, self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            check = False\n",
    "            if bit == 0:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.left:\n",
    "                    node = node.left\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.right\n",
    "            if check:\n",
    "                ans |= 1 << i\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n, q = len(nums), len(queries)\n",
    "        nums.sort()\n",
    "        queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda query: query[1])\n",
    "        \n",
    "        ans = [0] * q\n",
    "        t = Trie()\n",
    "        idx = 0\n",
    "        for x, m, qid in queries:\n",
    "            while idx < n and nums[idx] <= m:\n",
    "                t.insert(nums[idx])\n",
    "                idx += 1\n",
    "            if idx == 0:\n",
    "                # 字典树为空\n",
    "                ans[qid] = -1\n",
    "            else:\n",
    "                ans[qid] = t.getMaxXor(x)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    L = 30\n",
    "\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def insert(self, val: int):\n",
    "        node = self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if bit == 0:\n",
    "                if not node.left:\n",
    "                    node.left = Trie()\n",
    "                node = node.left\n",
    "            else:\n",
    "                if not node.right:\n",
    "                    node.right = Trie()\n",
    "                node = node.right\n",
    "    \n",
    "    def getMaxXor(self, val: int) -> int:\n",
    "        ans, node = 0, self\n",
    "        for i in range(Trie.L, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            check = False\n",
    "            if bit == 0:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.left:\n",
    "                    node = node.left\n",
    "                    check = True\n",
    "                else:\n",
    "                    node = node.right\n",
    "            if check:\n",
    "                ans |= 1 << i\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n, q = len(nums), len(queries)\n",
    "        nums.sort()\n",
    "        queries = sorted([(x, m, i) for i, (x, m) in enumerate(queries)], key=lambda query: query[1])\n",
    "        \n",
    "        ans = [0] * q\n",
    "        t = Trie()\n",
    "        idx = 0\n",
    "        for x, m, qid in queries:\n",
    "            while idx < n and nums[idx] <= m:\n",
    "                t.insert(nums[idx])\n",
    "                idx += 1\n",
    "            if idx == 0:\n",
    "                # 字典树为空\n",
    "                ans[qid] = -1\n",
    "            else:\n",
    "                ans[qid] = t.getMaxXor(x)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums.sort()\n",
    "        HIGH_BIT = 30\n",
    "\n",
    "        qrs = [q + [i] for i, q in enumerate(queries)]\n",
    "\n",
    "        qrs.sort(key=lambda x:x[1])\n",
    "\n",
    "        root = Trie()\n",
    "\n",
    "        def add(num: int):\n",
    "            curr = root\n",
    "            for k in range(HIGH_BIT, -1, -1):\n",
    "                bit = (num >> k) & 1\n",
    "                if bit == 1:\n",
    "                    if not curr.right:\n",
    "                        curr.right = Trie()\n",
    "                    curr = curr.right\n",
    "                else:\n",
    "                    if not curr.left:\n",
    "                        curr.left = Trie()\n",
    "                    curr = curr.left\n",
    "        \n",
    "        def check(num: int):\n",
    "            x = 0\n",
    "            curr = root\n",
    "            for k in range(HIGH_BIT, -1, -1):\n",
    "                bit = (num >> k) & 1\n",
    "                if bit == 1:\n",
    "                    if curr.left:\n",
    "                        curr = curr.left\n",
    "                        x = x * 2 + 1\n",
    "                    else:\n",
    "                        curr = curr.right\n",
    "                        x *= 2\n",
    "                else:\n",
    "                    if curr.right:\n",
    "                        curr = curr.right\n",
    "                        x = x * 2 + 1\n",
    "                    else:\n",
    "                        curr = curr.left\n",
    "                        x *= 2\n",
    "            return x\n",
    "\n",
    "        res = [0] * len(qrs)\n",
    "        idx = 0\n",
    "\n",
    "        for x, m, i in qrs:\n",
    "            while idx < len(nums) and nums[idx] <= m:\n",
    "                # print(nums[idx])\n",
    "                add(nums[idx])\n",
    "                idx += 1\n",
    "            if idx == 0:\n",
    "                res[i] = -1\n",
    "            else:\n",
    "                res[i] = check(x)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.left = None \n",
    "        self.right = None\n",
    "    def add(self, x: int) -> None:\n",
    "        for k in range(30, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            if bit == 0:\n",
    "                if not self.left:\n",
    "                    self.left = Trie()\n",
    "                self = self.left\n",
    "            else:\n",
    "                if not self.right:\n",
    "                    self.right = Trie()\n",
    "                self = self.right\n",
    "    def find(self, x: int) -> int:\n",
    "        if not self.left and not self.right:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        for k in range(30, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            if bit == 0:\n",
    "                if self.right:\n",
    "                    ans = ans * 2 + 1\n",
    "                    self = self.right\n",
    "                else:\n",
    "                    ans = ans * 2 \n",
    "                    self = self.left \n",
    "            else:\n",
    "                if self.left:\n",
    "                    ans = ans * 2 + 1\n",
    "                    self = self.left\n",
    "                else:\n",
    "                    ans = ans * 2\n",
    "                    self = self.right\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        f = list(zip(range(n), queries))\n",
    "        f.sort(key = lambda x: x[1][1])\n",
    "        ans = [0] * n \n",
    "        l = len(nums)\n",
    "        j = 0\n",
    "        print(f)\n",
    "        root = Trie()\n",
    "        nums.sort()\n",
    "        for i in range(n):\n",
    "            while j < l and nums[j] <= f[i][1][1]:\n",
    "                root.add(nums[j])\n",
    "                j += 1\n",
    "            ans[f[i][0]] = root.find(f[i][1][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self, val=0):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.minnum = 10**9 + 1\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def to2(num):\n",
    "            num2 = []\n",
    "            for _ in range(36):\n",
    "                num2.append(num % 2)\n",
    "                num //= 2\n",
    "            return num2\n",
    "\n",
    "        # 0 1\n",
    "        root = Tree()\n",
    "        # 建树\n",
    "        for num in nums:\n",
    "            num2 = to2(num)\n",
    "\n",
    "            node = root\n",
    "            tempnum = 0\n",
    "            tempk = 35\n",
    "            while num2:\n",
    "                if num2.pop():\n",
    "                    tempnum += 2**tempk\n",
    "                    if not node.right:\n",
    "                        node.right = Tree(tempnum)\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    if not node.left:\n",
    "                        node.left = Tree(tempnum)\n",
    "                    node = node.left\n",
    "                node.minnum = min(node.minnum, num)\n",
    "                tempk -= 1\n",
    "        \n",
    "        # def dfs(root):\n",
    "        #     de = deque()\n",
    "        #     de.append(root)\n",
    "        #     while de:\n",
    "        #         for _ in range(len(de)):\n",
    "        #             t = de.pop()\n",
    "        #             if t.left:\n",
    "        #                 de.appendleft(t.left)\n",
    "        #             if t.right:\n",
    "        #                 de.appendleft(t.right)\n",
    "        #             print(t.val, \"(%d)\" % t.minnum, end=\" \")\n",
    "        #         print()\n",
    "        # dfs(root)\n",
    "\n",
    "\n",
    "        ans = []\n",
    "        minnum = min(nums)\n",
    "        for num0, num2 in queries:\n",
    "            if num2 < minnum:\n",
    "                ans.append(-1)\n",
    "                continue\n",
    "\n",
    "            num1 = to2(num0)\n",
    "            node = root\n",
    "            while num1:\n",
    "                temp = num1.pop()\n",
    "                if not temp:\n",
    "                    if node.right and node.right.minnum <= num2:\n",
    "                        node = node.right\n",
    "                    else:\n",
    "                        node = node.left\n",
    "                else:\n",
    "                    if node.left and node.left.minnum <= num2:\n",
    "                        node = node.left\n",
    "                    else:\n",
    "                        node = node.right\n",
    "            ans.append(num0 ^ node.val)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self, val=0):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.minnum = 10**9 + 1\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def to2(num):\n",
    "            num2 = []\n",
    "            for _ in range(36):\n",
    "                num2.append(num % 2)\n",
    "                num //= 2\n",
    "            return num2\n",
    "\n",
    "        # 0 1\n",
    "        root = Tree()\n",
    "        # 建树\n",
    "        for num in nums:\n",
    "            num2 = to2(num)\n",
    "\n",
    "            node = root\n",
    "            tempnum = 0\n",
    "            tempk = 35\n",
    "            while num2:\n",
    "                if num2.pop():\n",
    "                    tempnum += 2**tempk\n",
    "                    if not node.right:\n",
    "                        node.right = Tree(tempnum)\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    if not node.left:\n",
    "                        node.left = Tree(tempnum)\n",
    "                    node = node.left\n",
    "                node.minnum = min(node.minnum, num)\n",
    "                tempk -= 1\n",
    "        \n",
    "        # def dfs(root):\n",
    "        #     de = deque()\n",
    "        #     de.append(root)\n",
    "        #     while de:\n",
    "        #         for _ in range(len(de)):\n",
    "        #             t = de.pop()\n",
    "        #             if t.left:\n",
    "        #                 de.appendleft(t.left)\n",
    "        #             if t.right:\n",
    "        #                 de.appendleft(t.right)\n",
    "        #             print(t.val, \"(%d)\" % t.minnum, end=\" \")\n",
    "        #         print()\n",
    "        # dfs(root)\n",
    "\n",
    "\n",
    "        ans = []\n",
    "        minnum = min(nums)\n",
    "        for num0, num2 in queries:\n",
    "            if num2 < minnum:\n",
    "                ans.append(-1)\n",
    "                continue\n",
    "\n",
    "            num1 = to2(num0)\n",
    "            node = root\n",
    "            while num1:\n",
    "                temp = num1.pop()\n",
    "                if not temp:\n",
    "                    if node.right and node.right.minnum <= num2:\n",
    "                        node = node.right\n",
    "                    else:\n",
    "                        node = node.left\n",
    "                else:\n",
    "                    if node.left and node.left.minnum <= num2:\n",
    "                        node = node.left\n",
    "                    else:\n",
    "                        node = node.right\n",
    "            ans.append(num0 ^ node.val)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], qs: List[List[int]]) -> List[int]:\n",
    "        n, m = len(nums), len(qs)\n",
    "        ans = [-1] * m\n",
    "        N = 30 * n\n",
    "        son = [[0] * 2 for _ in range(N)]\n",
    "        idx = 0\n",
    "        def insert(x):\n",
    "            p = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                u = x >> i & 1\n",
    "                # if p >= N:\n",
    "                #     print(idx)\n",
    "                if not son[p][u]:\n",
    "                    nonlocal idx\n",
    "                    idx += 1\n",
    "                    son[p][u] = idx\n",
    "                p = son[p][u]\n",
    "        \n",
    "        def query(x):\n",
    "            res = p = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                u = x >> i & 1\n",
    "                if son[p][u ^ 1]:\n",
    "                    res |= 1 << i\n",
    "                    p = son[p][u ^ 1]\n",
    "                else:\n",
    "                    p = son[p][u]\n",
    "            return res\n",
    "        l = 0\n",
    "        nums.sort()\n",
    "        for (xi, mi), i in sorted(zip(qs, range(n)), key = lambda x: x[0][1]):\n",
    "            # print(xi, mi, i)\n",
    "            while l < n and nums[l] <= mi:\n",
    "                insert(nums[l])\n",
    "                l += 1\n",
    "            if l:\n",
    "                ans[i] = query(xi)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def x2bin(self, s, bit_len):\n",
    "        return (bin(s)[2:].zfill(bit_len)[-bit_len:])\n",
    "\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums.sort(reverse = True)\n",
    "        queries = sorted([(*q, cnt) for cnt, q in enumerate(queries)], key=lambda x: x[1])\n",
    "        d = {}\n",
    "        res = []\n",
    "\n",
    "        for x, m, cnt in queries:\n",
    "            while nums and nums[-1]<=m:\n",
    "                p = d\n",
    "                for bit in self.x2bin(nums.pop(), 32):\n",
    "                    bit = int(bit)\n",
    "                    if bit not in p: p[bit] = {}\n",
    "                    p = p[bit]\n",
    "            tmp_res = ''\n",
    "            if d:\n",
    "                p = d                \n",
    "                for bit in self.x2bin(x, 32):\n",
    "                    bit = int(bit)\n",
    "                    if bit^1 in p: \n",
    "                        tmp_res += '1'\n",
    "                        p = p[bit^1]\n",
    "                    else:\n",
    "                        tmp_res += '0'\n",
    "                        p = p[bit]\n",
    "            tmp_res = int(tmp_res, 2) if tmp_res else -1\n",
    "            res.append((tmp_res, cnt))\n",
    "        return [i[0] for i in sorted(res, key=lambda x: x[1])]\n",
    "   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def x2bin(self, s, bit_len):\n",
    "        return (bin(s)[2:].zfill(bit_len)[-bit_len:])\n",
    "\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums.sort(reverse = True)\n",
    "        queries = sorted([(*q, cnt) for cnt, q in enumerate(queries)], key=lambda x: x[1])\n",
    "        d, res = {}, []\n",
    "        for x, m, cnt in queries:\n",
    "            while nums and nums[-1]<=m:\n",
    "                p = d\n",
    "                for bit in bin(nums.pop())[2:].zfill(30)[-30:]:\n",
    "                    if bit not in p: p[bit] = {}\n",
    "                    p = p[bit]\n",
    "            s = ''\n",
    "            if d:\n",
    "                p = d                \n",
    "                for bit in bin(x)[2:].zfill(30)[-30:]:\n",
    "                    if '01'[bit=='0'] in p: \n",
    "                        s += '1'\n",
    "                        p = p['01'[bit=='0']]\n",
    "                    else:\n",
    "                        s += '0'\n",
    "                        p = p[bit]\n",
    "            res.append(((int(s, 2) if s else -1), cnt))\n",
    "        return [i[0] for i in sorted(res, key=lambda x: x[1])]\n",
    "   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def x2bin(self, s, bit_len):\n",
    "        return (bin(s)[2:].zfill(bit_len)[-bit_len:])\n",
    "\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums.sort(reverse = True)\n",
    "        queries = sorted([(*q, cnt) for cnt, q in enumerate(queries)], key=lambda x: x[1])\n",
    "        d, res = {}, []\n",
    "        for x, m, cnt in queries:\n",
    "            while nums and nums[-1]<=m:\n",
    "                p = d\n",
    "                for bit in bin(nums.pop())[2:].zfill(30)[-30:]:\n",
    "                    if bit not in p: p[bit] = {}\n",
    "                    p = p[bit]\n",
    "            s = ''\n",
    "            if d:\n",
    "                p = d                \n",
    "                for bit in bin(x)[2:].zfill(30)[-30:]:\n",
    "                    if '01'[bit=='0'] in p: \n",
    "                        s += '1'\n",
    "                        p = p['01'[bit=='0']]\n",
    "                    else:\n",
    "                        s += '0'\n",
    "                        p = p[bit]\n",
    "            s = int(s, 2) if s else -1\n",
    "            res.append((s, cnt))\n",
    "        return [i[0] for i in sorted(res, key=lambda x: x[1])]\n",
    "   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def x2bin(self, s, bit_len):\n",
    "        return (bin(s)[2:].zfill(bit_len)[-bit_len:])\n",
    "\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums.sort(reverse = True)\n",
    "        queries = sorted([(*q, cnt) for cnt, q in enumerate(queries)], key=lambda x: x[1])\n",
    "        d, res = {}, []\n",
    "        for x, m, cnt in queries:\n",
    "            while nums and nums[-1]<=m:\n",
    "                p = d\n",
    "                for bit in self.x2bin(nums.pop(), 30):\n",
    "                    if bit not in p: p[bit] = {}\n",
    "                    p = p[bit]\n",
    "            s = ''\n",
    "            if d:\n",
    "                p = d                \n",
    "                for bit in self.x2bin(x, 30):\n",
    "                    if '01'[bit=='0'] in p: \n",
    "                        s += '1'\n",
    "                        p = p['01'[bit=='0']]\n",
    "                    else:\n",
    "                        s += '0'\n",
    "                        p = p[bit]\n",
    "            s = int(s, 2) if s else -1\n",
    "            res.append((s, cnt))\n",
    "        return [i[0] for i in sorted(res, key=lambda x: x[1])]\n",
    "   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        m = len(queries)\n",
    "        r = 30\n",
    "        d = {}\n",
    "        ans = [-1] * m\n",
    "        nums.sort()\n",
    "        idx = sorted(range(m), key=lambda x:queries[x][1])\n",
    "\n",
    "        def insert(x):\n",
    "            root = d\n",
    "            for i in range(r, -1, -1):\n",
    "                b = x >> i & 1\n",
    "                if b not in root:\n",
    "                    root[b] = {}\n",
    "                root = root[b]\n",
    "        \n",
    "        j = 0\n",
    "        for i in idx:\n",
    "            x, m = queries[i]\n",
    "            while j < n and nums[j] <= m:\n",
    "                insert(nums[j])\n",
    "                j += 1\n",
    "            if j == 0:\n",
    "                continue\n",
    "            res = 0\n",
    "            root = d\n",
    "            for k in range(r, -1, -1):\n",
    "                t = x >> k & 1\n",
    "                if t^1 in root:\n",
    "                    res |= 1 << k\n",
    "                    root = root[t^1]\n",
    "                else:\n",
    "                    root = root[t]\n",
    "            ans[i] = res\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieZeroOneXorMax:\n",
    "    # 模板：使用01Trie维护与查询数组最大异或值\n",
    "    def __init__(self, n):\n",
    "        # 使用字典数据结构实现\n",
    "        self.dct = dict()\n",
    "        # 确定序列长度\n",
    "        self.n = n\n",
    "        self.inf = inf\n",
    "        return\n",
    "\n",
    "    def add(self, num):\n",
    "        cur = self.dct\n",
    "        for i in range(self.n, -1, -1):\n",
    "            w = 1 if num & (1 << i) else 0\n",
    "            if w not in cur:\n",
    "                cur[w] = dict()\n",
    "            cur = cur[w]\n",
    "        return\n",
    "\n",
    "    def query_xor_max(self, num):\n",
    "        # 计算与num异或可以得到的最大值\n",
    "        cur = self.dct\n",
    "        ans = 0\n",
    "        for i in range(self.n, -1, -1):\n",
    "            w = 1 if num & (1 << i) else 0\n",
    "            if 1 - w in cur:\n",
    "                cur = cur[1 - w]\n",
    "                ans |= (1 << i)\n",
    "            elif w in cur:\n",
    "                cur = cur[w]\n",
    "            else:\n",
    "                return 0\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        tree = TrieZeroOneXorMax(34)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        m = len(queries)\n",
    "        ans = [-1]*m\n",
    "        ind = list(range(m))\n",
    "        ind.sort(key=lambda it: queries[it][1])\n",
    "        for j in ind:\n",
    "            x, m = queries[j]\n",
    "            while i < n and nums[i] <= m:\n",
    "                tree.add(nums[i])\n",
    "                i += 1\n",
    "            if not i:\n",
    "                continue\n",
    "            ans[j] = tree.query_xor_max(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        t = {}\n",
    "        def insert(num):\n",
    "            cur = t\n",
    "            for i in range(30, -1, -1):\n",
    "                bit = num >> i & 1\n",
    "                if bit not in cur:\n",
    "                    cur[bit] = {}\n",
    "                cur = cur[bit]\n",
    "\n",
    "        def get_max(num):\n",
    "            cur = t\n",
    "            res = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                bit = num >> i & 1\n",
    "                opp_bit = 1 - bit\n",
    "                if opp_bit in cur:\n",
    "                    cur = cur[opp_bit]\n",
    "                    res |= 1 << i\n",
    "                else:\n",
    "                    cur = cur[bit]\n",
    "            return res\n",
    "        nums.sort()\n",
    "        n = len(queries)\n",
    "        ans = [-1] * n\n",
    "        j = 0\n",
    "        for idx, (x, m) in sorted(zip(range(n), queries), key=lambda x: x[1][1]):\n",
    "            while j < len(nums) and nums[j] <= m:\n",
    "                insert(nums[j])\n",
    "                j += 1\n",
    "            if j > 0:\n",
    "                res = get_max(x)\n",
    "                ans[idx] = res\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "\n",
    "    def add(self, x):\n",
    "        node = self.root\n",
    "        for i in range(31, -1, -1):\n",
    "            tar = (x >> i) & 1\n",
    "            if tar not in node:\n",
    "                node[tar] = {}\n",
    "            node = node[tar]\n",
    "\n",
    "    def query(self, y):\n",
    "        res = 0\n",
    "        node = self.root\n",
    "        # if not node:\n",
    "        #     return -1\n",
    "        for i in range(31, -1, -1):\n",
    "            tar = ((y >> i) & 1) ^ 1\n",
    "            tran = tar ^ 1\n",
    "            if tar in node:\n",
    "                node = node[tar]\n",
    "                res ^= (1 << i)\n",
    "            elif tran in node:\n",
    "                node = node[tran]\n",
    "                # res ^= (0 << i)\n",
    "            else:\n",
    "                return -1\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        trie = Trie()\n",
    "        for idx, (x, m) in sorted(enumerate(queries), key=lambda p: p[1][1]):\n",
    "            while i < len(nums) and nums[i] <= m:\n",
    "                trie.add(nums[i])\n",
    "                i += 1\n",
    "            ans[idx] = trie.query(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "\n",
    "    def add(self, x):\n",
    "        node = self.root\n",
    "        for i in range(31, -1, -1):\n",
    "            tar = (x >> i) & 1\n",
    "            if tar not in node:\n",
    "                node[tar] = {}\n",
    "            node = node[tar]\n",
    "\n",
    "    def query(self, y):\n",
    "        res = 0\n",
    "        node = self.root\n",
    "        if not node:\n",
    "            return -1\n",
    "        for i in range(31, -1, -1):\n",
    "            tar = ((y >> i) & 1) ^ 1\n",
    "            tran = tar ^ 1\n",
    "            if tar in node:\n",
    "                node = node[tar]\n",
    "                res ^= (1 << i)\n",
    "            elif tran in node:\n",
    "                node = node[tran]\n",
    "            \n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        trie = Trie()\n",
    "        for idx, (x, m) in sorted(enumerate(queries), key=lambda p: p[1][1]):\n",
    "            while i < len(nums) and nums[i] <= m:\n",
    "                trie.add(nums[i])\n",
    "                i += 1\n",
    "            ans[idx] = trie.query(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        trie={}\n",
    "        def insert(x):\n",
    "            root=trie\n",
    "            for i in range(32,-1,-1):\n",
    "                u=x>>i&1\n",
    "                if u not in root:\n",
    "                    root[u]={}\n",
    "                root=root[u]\n",
    "        \n",
    "        def query(x):\n",
    "            root=trie\n",
    "            # if not root:return 0\n",
    "            ans=0\n",
    "            for i in range(32,-1,-1):\n",
    "                u=x>>i&1\n",
    "                if 1-u in root:\n",
    "                    ans=ans*2+1\n",
    "                    root=root[1-u]\n",
    "                else:\n",
    "                    ans=ans*2\n",
    "                    root=root[u]\n",
    "            return ans\n",
    "\n",
    "\n",
    "        nums.sort()\n",
    "        arr=[]\n",
    "        for i,[x,m] in enumerate(queries):\n",
    "            arr.append((i,x,m))\n",
    "        arr.sort(key=lambda x:x[2])\n",
    "        # print(nums,arr)\n",
    "        n=len(nums)\n",
    "        res=[-1]*len(queries)\n",
    "        j=0\n",
    "        for i,x,m in arr:\n",
    "            while j<n and nums[j]<=m:\n",
    "                insert(nums[j])\n",
    "                j+=1\n",
    "            if j>0:\n",
    "                ans=query(x)\n",
    "                res[i]=ans\n",
    "        # print(trie)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.dct = dict()\n",
    "        return\n",
    "\n",
    "    def update(self, num):\n",
    "        st = bin(num)[2:]\n",
    "        word = (32-len(st))*\"0\" + st\n",
    "        cur = self.dct\n",
    "        for w in word:\n",
    "            if w not in cur:\n",
    "                cur[w] = dict()\n",
    "            cur = cur[w]\n",
    "        return\n",
    "\n",
    "    def query(self, num):\n",
    "        st = bin(num)[2:]\n",
    "        word = (32-len(st))*\"0\" + st\n",
    "        cur = self.dct\n",
    "        pre = \"\"\n",
    "        for w in word:\n",
    "            s = str(1-int(w))\n",
    "            if s in cur:\n",
    "                cur = cur[s]\n",
    "                pre += \"1\"\n",
    "            else:\n",
    "                cur = cur[w]\n",
    "                pre += \"0\"\n",
    "        return int('0b'+pre, 2)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        trie = Trie()\n",
    "        m = len(queries)\n",
    "        for i in range(m):\n",
    "            queries[i].append(i)\n",
    "        queries.sort(key=lambda x: x[1])\n",
    "        ans = []\n",
    "        j = 0\n",
    "        for x, m, i in queries:\n",
    "            while j < n and nums[j]<=m:\n",
    "                trie.update(nums[j])\n",
    "                j += 1\n",
    "            if trie.dct:\n",
    "                ans.append([i, trie.query(x)])\n",
    "            else:\n",
    "                ans.append([i, -1])\n",
    "        ans.sort()\n",
    "        return [a[1] for a in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.dct = dict()\n",
    "        return\n",
    "\n",
    "    def update(self, num):\n",
    "        st = bin(num)[2:]\n",
    "        word = (32-len(st))*\"0\" + st\n",
    "        cur = self.dct\n",
    "        for w in word:\n",
    "            if w not in cur:\n",
    "                cur[w] = dict()\n",
    "            cur = cur[w]\n",
    "        return\n",
    "\n",
    "    def query(self, num):\n",
    "        st = bin(num)[2:]\n",
    "        word = (32-len(st))*\"0\" + st\n",
    "        cur = self.dct\n",
    "        pre = \"\"\n",
    "        for w in word:\n",
    "            s = str(1-int(w))\n",
    "            if s in cur:\n",
    "                cur = cur[s]\n",
    "                pre += \"1\"\n",
    "            else:\n",
    "                cur = cur[w]\n",
    "                pre += \"0\"\n",
    "        return int('0b'+pre, 2)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param queries:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        q = []\n",
    "\n",
    "        for k, v in enumerate(queries):\n",
    "            q.append((k, v[0], v[1]))\n",
    "        q.sort(key=lambda x: x[2])\n",
    "        nums.sort()\n",
    "        dq1 = deque(nums)\n",
    "        bt = Trie()\n",
    "        ret = []\n",
    "        for i in q:\n",
    "            while dq1 and dq1[0] <= i[2]:\n",
    "                cur = dq1.popleft()\n",
    "                bt.update(cur)\n",
    "            if bt.dct:\n",
    "                ret.append((bt.query(i[1]), i[0]))\n",
    "            else:\n",
    "                ret.append((-1, i[0]))\n",
    "        ret.sort(key=lambda x: x[1])\n",
    "        return [i[0] for i in ret]\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.maximizeXor(nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.dct = dict()\n",
    "        return\n",
    "\n",
    "    def update(self, num):\n",
    "        st = bin(num)[2:]\n",
    "        word = (32-len(st))*\"0\" + st\n",
    "        cur = self.dct\n",
    "        for w in word:\n",
    "            if w not in cur:\n",
    "                cur[w] = dict()\n",
    "            cur = cur[w]\n",
    "        return\n",
    "\n",
    "    def query(self, num):\n",
    "        st = bin(num)[2:]\n",
    "        word = (32-len(st))*\"0\" + st\n",
    "        cur = self.dct\n",
    "        pre = \"\"\n",
    "        for w in word:\n",
    "            s = str(1-int(w))\n",
    "            if s in cur:\n",
    "                cur = cur[s]\n",
    "                pre += \"1\"\n",
    "            else:\n",
    "                cur = cur[w]\n",
    "                pre += \"0\"\n",
    "        return int('0b'+pre, 2)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param queries:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        q = []\n",
    "        nums = list(set(nums))\n",
    "        for k, v in enumerate(queries):\n",
    "            q.append((k, v[0], v[1]))\n",
    "        q.sort(key=lambda x: x[2])\n",
    "        nums.sort()\n",
    "        dq1 = deque(nums)\n",
    "        bt = Trie()\n",
    "        ret = []\n",
    "        for i in q:\n",
    "            while dq1 and dq1[0] <= i[2]:\n",
    "                cur = dq1.popleft()\n",
    "                bt.update(cur)\n",
    "            if bt.dct:\n",
    "                ret.append((bt.query(i[1]), i[0]))\n",
    "            else:\n",
    "                ret.append((-1, i[0]))\n",
    "        ret.sort(key=lambda x: x[1])\n",
    "        return [i[0] for i in ret]\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.maximizeXor(nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = (10 ** 9).bit_length()\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.next = [None] * 2\n",
    "        self.counter = 0\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    \n",
    "    def insert(self, num):\n",
    "        node = self.root\n",
    "        for bit in range(N, -1, -1):\n",
    "            idx = (num >> bit) & 1\n",
    "            if node.next[idx] is None:\n",
    "                node.next[idx] = Node()\n",
    "            node = node.next[idx]\n",
    "            node.counter += 1\n",
    "    \n",
    "    def delete(self, num):\n",
    "        node = self.root\n",
    "        for bit in range(N, -1, -1):\n",
    "            idx = (num >> bit) & 1\n",
    "            node = node.next[idx]\n",
    "            node.counter -= 1\n",
    "\n",
    "    def query(self, num):\n",
    "        ans = 0\n",
    "        node = self.root\n",
    "        for bit in range(N, -1, -1):\n",
    "            idx = (num >> bit) & 1\n",
    "            other = 1 - idx\n",
    "            if node.next[other] is None or not node.next[other].counter:\n",
    "                node = node.next[idx]\n",
    "                if node is None:\n",
    "                    return -1\n",
    "            else:\n",
    "                node = node.next[other]\n",
    "                ans |= 1 << bit\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums.sort()\n",
    "        tree = Trie()\n",
    "        n = len(queries)\n",
    "        indices = sorted(range(n), key=lambda x: queries[x][1])\n",
    "        ans = [-1] * n\n",
    "        lo = 0\n",
    "        for idx in indices:\n",
    "            num, bound = queries[idx]\n",
    "            while lo < len(nums) and nums[lo] <= bound:\n",
    "                tree.insert(nums[lo])\n",
    "                lo += 1\n",
    "            ans[idx] = tree.query(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BTree:\n",
    "    def __init__(self):\n",
    "        self.node = [None, None]\n",
    "        self.val = 0\n",
    "    \n",
    "    def add(self, a):\n",
    "        i = 30\n",
    "        cur = self\n",
    "        while i >= 0:\n",
    "            j = (a >> i) & 1\n",
    "            if cur.node[j] is None:\n",
    "                cur.node[j] = BTree()\n",
    "            cur = cur.node[j]\n",
    "            i -= 1\n",
    "        cur.val = a\n",
    "    \n",
    "    def maxXor(self, x):\n",
    "        ans = 0\n",
    "        i = 30\n",
    "        cur = self\n",
    "        while i >= 0:\n",
    "            j = (x >> i) & 1\n",
    "            if cur.node[1 - j] is not None:\n",
    "                cur = cur.node[1 - j]\n",
    "            else:\n",
    "                cur = cur.node[j]\n",
    "            i -= 1\n",
    "        return cur.val ^ x\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        m = len(nums)\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        ans = [-1] * n\n",
    "        bt = BTree()\n",
    "        j = 0\n",
    "        for i in sorted(range(n), key = lambda x: queries[x][1]):\n",
    "            while j < m and nums[j] <= queries[i][1]:\n",
    "                bt.add(nums[j])\n",
    "                j += 1\n",
    "            # print(j, queries[i])\n",
    "            if j > 0:   ans[i] = bt.maxXor(queries[i][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ans = [-1] * n\n",
    "        nums.sort()\n",
    "        j, nn = 0, len(nums)\n",
    "        root = Trie()\n",
    "        for i, (x, m) in sorted(enumerate(queries), key=lambda y: y[1][1]):\n",
    "            while j < nn and nums[j] <= m:\n",
    "                # add to trie\n",
    "                tmp = root\n",
    "                for k in range(30, -1, -1):\n",
    "                    d = (nums[j] >> k) & 1\n",
    "                    if not tmp.children[d]:\n",
    "                        tmp.children[d] = Trie()\n",
    "                    tmp = tmp.children[d]\n",
    "                j += 1\n",
    "\n",
    "            if j == 0:\n",
    "                continue\n",
    "\n",
    "            # search ans\n",
    "            tmp = root\n",
    "            ans[i] = 0\n",
    "            for k in range(30, -1, -1):\n",
    "                d = (x >> k) & 1\n",
    "                if tmp.children[d ^ 1]:\n",
    "                    tmp = tmp.children[d ^ 1]\n",
    "                    ans[i] |= 1 << k\n",
    "                else:\n",
    "                    tmp = tmp.children[d]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.min = inf\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        root = Trie()\n",
    "        for num in nums:\n",
    "            # print(num)\n",
    "            node = root\n",
    "            for i in range(30, -1, -1):\n",
    "                cur = num >> i & 1\n",
    "                if node.children[cur] is None:\n",
    "                    node.children[cur] = Trie()\n",
    "                node = node.children[cur]\n",
    "                # print(num)\n",
    "                node.min = min(node.min, num)\n",
    "        ans = []\n",
    "        for num, limit in queries:\n",
    "            node = root\n",
    "            res = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                digit = num >> i & 1\n",
    "                if digit:\n",
    "                    # 选择0作为这一位的异或\n",
    "                    if node.children[0]:\n",
    "                        res |= 1 << i\n",
    "                        node = node.children[0]\n",
    "                    elif node.children[1].min > limit:\n",
    "                        res = -1\n",
    "                        break\n",
    "                    else:\n",
    "                        node = node.children[1]\n",
    "                else:\n",
    "                    if node.children[1] and node.children[1].min <= limit:\n",
    "                        res |= 1 << i\n",
    "                        node = node.children[1]\n",
    "                    elif not node.children[0]:\n",
    "                        res = -1\n",
    "                        break\n",
    "                    else:\n",
    "                        node = node.children[0]\n",
    "            ans.append(res)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.nxts = [None]*2\n",
    "        self.mi = sys.maxsize\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.head = Node()\n",
    "    \n",
    "    def add(self, num):\n",
    "        cur = self.head\n",
    "        cur.mi = min(cur.mi, num)\n",
    "        for i in range(30, -1, -1):\n",
    "            p = (num >> i) & 1\n",
    "            if cur.nxts[p] is None:\n",
    "                cur.nxts[p] = Node()\n",
    "            cur = cur.nxts[p]\n",
    "            cur.mi = min(cur.mi, num)\n",
    "\n",
    "    def get_xor_max_less_num(self, query, m):\n",
    "        cur = self.head\n",
    "        if cur.mi > m:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        for i in range(30, -1, -1):\n",
    "            p = (query >> i) & 1\n",
    "            best = p^1\n",
    "            actual = best if cur.nxts[best] is not None and cur.nxts[best].mi <= m else best^1\n",
    "            ans |= ((p ^ actual) << i)\n",
    "            cur = cur.nxts[actual]\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        trie = Trie()\n",
    "        for i in range(len(nums)):\n",
    "            trie.add(nums[i])\n",
    "        for i in range(len(queries)):\n",
    "            ans.append(trie.get_xor_max_less_num(queries[i][0], queries[i][1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.children: list[Node] = [None] * 2\r\n",
    "\r\n",
    "def search(i: int, x: int, m: int, cur: int, node: Node) -> int:\r\n",
    "    if i < 0: return cur ^ x\r\n",
    "    j = ((x >> i) & 1) ^ 1\r\n",
    "    cur = (cur << 1) | j\r\n",
    "    if node.children[j] is not None and cur <= m >> i:\r\n",
    "        ret = search(i - 1, x, m, cur, node.children[j])\r\n",
    "        if ret != -1: return ret\r\n",
    "    return -1 if node.children[j ^ 1] is None or cur ^ 1 > m >> i else search(i - 1, x, m, cur ^ 1, node.children[j ^ 1])\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\r\n",
    "        root = Node()\r\n",
    "        for num in nums:\r\n",
    "            node = root\r\n",
    "            for i in range(29, -1, -1):\r\n",
    "                j = (num >> i) & 1\r\n",
    "                if node.children[j] is None:\r\n",
    "                    node.children[j] = Node()\r\n",
    "                node = node.children[j]\r\n",
    "        \r\n",
    "        return [search(29, x, m, 0, root) for x, m in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.min = inf\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        root = Trie()\n",
    "        for num in nums:\n",
    "            # print(num)\n",
    "            node = root\n",
    "            for i in range(30, -1, -1):\n",
    "                cur = num >> i & 1\n",
    "                if node.children[cur] is None:\n",
    "                    node.children[cur] = Trie()\n",
    "                node = node.children[cur]\n",
    "                # print(num)\n",
    "                node.min = node.min if node.min < num else num\n",
    "        ans = []\n",
    "        for num, limit in queries:\n",
    "            node = root\n",
    "            res = 0\n",
    "            for i in range(30, -1, -1):\n",
    "                digit = num >> i & 1\n",
    "                if digit:\n",
    "                    # 选择0作为这一位的异或\n",
    "                    if node.children[0]:\n",
    "                        res |= 1 << i\n",
    "                        node = node.children[0]\n",
    "                    elif node.children[1].min > limit:\n",
    "                        res = -1\n",
    "                        break\n",
    "                    else:\n",
    "                        node = node.children[1]\n",
    "                else:\n",
    "                    if node.children[1] and node.children[1].min <= limit:\n",
    "                        res |= 1 << i\n",
    "                        node = node.children[1]\n",
    "                    elif not node.children[0]:\n",
    "                        res = -1\n",
    "                        break\n",
    "                    else:\n",
    "                        node = node.children[0]\n",
    "            ans.append(res)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self) -> None:\n",
    "        self.children: list[Node] = [None] * 2\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        pnt = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        root = Node()\n",
    "        res = [0] * len(queries)\n",
    "        qry = sorted(enumerate(queries), key=lambda q: q[1][1])\n",
    "\n",
    "        for idx, (x, m) in qry:\n",
    "            while pnt < n and nums[pnt] <= m:\n",
    "                node = root\n",
    "                for i in range(29, -1, -1):\n",
    "                    j = (nums[pnt] >> i) & 1\n",
    "                    if node.children[j] is None:\n",
    "                        node.children[j] = Node()\n",
    "                    node = node.children[j]\n",
    "                pnt += 1\n",
    "\n",
    "            node = root\n",
    "            for i in range(29, -1, -1):\n",
    "                j = ((x >> i) & 1) ^ 1\n",
    "                if node.children[j] is not None:\n",
    "                    node = node.children[j]\n",
    "                    res[idx] |= 1 << i\n",
    "                elif node.children[j ^ 1] is not None:\n",
    "                    node = node.children[j ^ 1]\n",
    "                else:\n",
    "                    res[idx] = -1\n",
    "                    break\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode():\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    \n",
    "    def insert(self, x):\n",
    "        cur = self.root\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (x >> i) & 1\n",
    "            if not cur.children[bit]:\n",
    "                cur.children[bit] = TrieNode()\n",
    "            cur = cur.children[bit]\n",
    "    \n",
    "    \n",
    "    def get_max_xor(self, x):\n",
    "        cur = self.root\n",
    "        ans = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (x >> i) & 1\n",
    "            flip_bit = 1 - bit\n",
    "            if cur.children[flip_bit]:\n",
    "                cur = cur.children[flip_bit]\n",
    "                ans |= 1 << i\n",
    "            else:\n",
    "                if not cur.children[bit]:\n",
    "                    return -1\n",
    "                cur = cur.children[bit]\n",
    "\n",
    "        return ans \n",
    "        \n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ans = [-1] * n\n",
    "        nums.sort()\n",
    "        trie = Trie()\n",
    "        j = 0\n",
    "        for i, (a, b) in sorted(enumerate(queries), key=lambda x: x[1][1]):\n",
    "            while j < len(nums) and nums[j] <= b:\n",
    "                trie.insert(nums[j])\n",
    "                j += 1\n",
    "            ans[i] = trie.get_max_xor(a)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    MAX_BIT = 32\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "        self.cnt = 0\n",
    "\n",
    "    def insert(self, num):\n",
    "        cur = self.root\n",
    "        cur.cnt += 1\n",
    "        for i in range(self.MAX_BIT, -1, -1):\n",
    "            v = (num >> i) & 1\n",
    "            if not cur.children[v]:\n",
    "                cur.children[v] = Node()\n",
    "            cur = cur.children[v]\n",
    "            cur.cnt += 1\n",
    "\n",
    "    def remove(self, num):\n",
    "        cur = self.root\n",
    "        cur.cnt -= 1\n",
    "        for i in range(self.MAX_BIT, -1, -1):\n",
    "            v = (num >> i) & 1\n",
    "            cur = cur.children[v]\n",
    "            cur.cnt -= 1\n",
    "\n",
    "    def max_xor(self, num):\n",
    "        cur = self.root\n",
    "        ans = 0\n",
    "        for i in range(self.MAX_BIT, -1, -1):\n",
    "            cv = (num >> i) & 1\n",
    "            if cur.children[cv ^ 1] and cur.children[cv ^ 1].cnt > 0:\n",
    "                cur = cur.children[cv ^ 1]\n",
    "                ans |= (1 << i)\n",
    "            else:\n",
    "                cur = cur.children[cv]\n",
    "        return ans\n",
    "\n",
    "class Solution(object):\n",
    "    def maximizeXor(self, nums, queries):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type queries: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        t = Trie()\n",
    "        nums = sorted(nums)\n",
    "        l = 0\n",
    "        q = len(queries)\n",
    "        res = [0] * q\n",
    "\n",
    "        queries = zip(queries, range(q))\n",
    "        queries = sorted(queries, key=lambda x: x[0][1])\n",
    "        for (x,m),idx in queries:\n",
    "            while l < len(nums) and nums[l] <= m:\n",
    "                t.insert(nums[l])\n",
    "                l += 1\n",
    "      \n",
    "            if  (l==0 and nums[l] > m):\n",
    "                res[idx] = -1\n",
    "            else:\n",
    "                \n",
    "                res[idx] = t.max_xor(x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.bit = [None] * 2\n",
    "\n",
    "    def insert(self, num):\n",
    "        node = self\n",
    "        for i in range(30, -1, -1):\n",
    "            d = num >> i & 1\n",
    "            if not node.bit[d]:\n",
    "                node.bit[d] = Trie()\n",
    "            node = node.bit[d]\n",
    "    \n",
    "    def query(self, num):\n",
    "        node = self\n",
    "        ans = 0\n",
    "        for i in range(30, -1, -1):\n",
    "            d = num >> i & 1\n",
    "            if node.bit[d ^ 1]:\n",
    "                ans |= 1 << i\n",
    "                node = node.bit[d ^ 1]\n",
    "            else:\n",
    "                node = node.bit[d]\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = sorted(set(nums))\n",
    "        order = sorted((m, x, i) for i, (x, m) in enumerate(queries))\n",
    "        root = Trie()\n",
    "        i = 0\n",
    "        ans = [-1] * len(order)\n",
    "        for m, x, idx in order:\n",
    "            if m < nums[0]:\n",
    "                continue\n",
    "            while i < len(nums) and nums[i] <= m:\n",
    "                root.insert(nums[i])\n",
    "                i += 1\n",
    "            ans[idx] = root.query(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeXor(self, a: List[int], q: List[List[int]]) -> List[int]:\n",
    "        s = {}\n",
    "        def fix(j, x):\n",
    "            nonlocal s \n",
    "            if j not in s:\n",
    "                s[j] = {}\n",
    "                    \n",
    "            if 'm' not in s:\n",
    "                s['m'] = x\n",
    "            else:\n",
    "                s['m'] = min(x, s['m'])  \n",
    "            s = s[j]\n",
    "        for j in set(a):\n",
    "            t = s \n",
    "            for i in range(32)[::-1]:\n",
    "                fix((j>>i)&1, j) \n",
    "            s['m'] = j \n",
    "            s = t \n",
    "        def turn(j, m):\n",
    "            nonlocal s \n",
    "            if (j in s) and (s[j]['m']<=m):\n",
    "                s = s[j] \n",
    "                return 1 \n",
    "            else:\n",
    "                s = s[1-j]\n",
    "                return 0\n",
    "        def find(x, m):\n",
    "            nonlocal s \n",
    "            t = s \n",
    "            ans = 0 \n",
    "            if ('m' not in s) or (s['m']>m):\n",
    "                return -1 \n",
    "            for i in range(32)[::-1]: \n",
    "                    tmp = turn(1 - ((x>>i)&1), m)\n",
    "                    if tmp:\n",
    "                        ans += (1<<i) \n",
    "            s = t \n",
    "            return ans \n",
    "     \n",
    "        ans = [find(x, m) for x, m in q]\n",
    "        return ans \n",
    "          \n",
    "                    \n",
    "\n",
    "        \n",
    "                        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
